package leetcode.weekly.week297;

//Solution2Test
public class Solution2 {
	int[][] grid;
	int[][] moveCost;
	int m, n;

	// Solution2Test
	public int minPathCost(int[][] grid, int[][] moveCost) {
		this.grid = grid;
		this.moveCost = moveCost;
		m = grid.length;
		n = grid[0].length;
		int ans = Integer.MAX_VALUE;
		Integer[][] dp = new Integer[m + 1][n + 1];
		for (int i = 0; i < n; i++) {
			int val = grid[0][i];
			int x = 0, y = i;
			int cur = this.minPathCost(x, y, dp) + val;
			ans = Math.min(cur, ans);
		}
		return ans;
	}

	private int minPathCost(int x, int y, Integer[][] dp) {
		if (x == m - 1) {
			return 0;
		}
		if (dp[x][y] != null) {
			return dp[x][y];
		}
		int ans = Integer.MAX_VALUE;
		int val = this.grid[x][y];
		for (int i = 0; i < n; i++) {
			int cost = this.moveCost[val][i];
			int v = this.grid[x + 1][i];
			int cur = cost + this.minPathCost(x + 1, i, dp) + v;
			ans = Math.min(ans, cur);
		}
		dp[x][y] = ans;
		return ans;
	}

}
